This invention relates generally to compressing color video data and, more specifically, to varying the degree of compression as a function of the color characteristics of the video data being compressed.
Color video animations or videotapes of images or scenes can be used to enhance the realism and/or usefulness of computer generated displays and graphics. These video images are typically stored as a stream of digital color video data on a storage device such as a CD-ROM disk in a retrievable format. When desired by the viewer, or when directed by the software program, the color video data representing the video image is retrieved from the storage device and displayed on a display device, such as a video monitor. In practice, the video data is not displayed continuously, but is divided into a series of frames. Each frame of video data comprises the necessary information to display a single screen, or xe2x80x9csnapshotxe2x80x9d of the video on the display device. Displaying a sequential series of frames in rapid succession can create the illusion of moving pictures.
The quality and realism of the displayed image is a function of the resolution of the display device and the number of colors that the display device is capable of displaying. Typically, reasonable image resolution can be achieved with a display device that displays an image where the image consists of 480 horizontal lines of 640 pixels, or picture elements, per line, although images suitable for some video games may be displayed on devices having resolutions as low as 240 horizontal lines of 320 pixels. Recently, higher resolution display devices capable of displaying 1024 lines of 1280 pixels per line have become commonly available. Where only a simple, two-tone monochrome image is desired, each pixel can be represented by a single bit of video data, since the pixel is either illuminated or dark, depending on the image. Typically, however, monochrome images are displayed using eight bits of data to represent each pixel, allowing each pixel of the image to be displayed in one of a possible 256 shades of a single color. Images displayed in color are much more exciting and visually pleasing than monochrome images, especially when used to enhance the realism of video games and simulations. Substantially more information in the form of digital video color data, however, is required to reproduce color images. In the simplest case, at least three times as much digital data must be used to define a color to be displayed by an individual pixel, since each color consists of a combination of the primary colors red, blue and green, and each of these colors must be defined by digital data. Current display devices, using the RGB (red-blue-green) format are capable of providing as many as 16,777,216 colors by using 24 bits of color video data to define each pixel.
Where relatively static images are to be displayed, the amount of color video data required is not a critical factor in the performance of the software program. However, where a video animation or moving image is desired, the video will appear jerky, unnatural and unrealistic if the video data is not displayed at a rate of at least 30 frames per second, the NTSC television standard. A single video clip lasting one minute must thus be composed of at least 1800 frames of video color data. This enormous amount of video color data must be stored on and retrieved from a CD-ROM or other device having enough storage space to hold all the video color data for the video clip.
A further problem is that storage devices such as CD-ROMs have limited data transfer rates, typically a maximum of about 600,000 bits per second. Where the data cannot be retrieved and displayed rapidly enough, the formation of the video image may stall momentarily while the color video data is being transferred from the storage device to the display device, and detracts from the realism of the displayed video images. In order to increase the effective speed of such storage devices and decrease the wait time for generating a moving color video display, numerous compression and decompression techniques to reduce the amount of color video data that must be stored and retrieved have been proposed. Some compression techniques divide a picture or image into a matrix of blocks, each of which is in turn divided into a matrix of picture elements or pixels. The picture or image can be converted into digital data which can then be used to generate a video display of the original picture, wherein certain information must be encoded for every pixel of every block. The amount of data required per pixel and the quality in detail of the picture that can be generated from the data are important characteristics of any compression system. In some instances, the data is compressed in a uniform manner block-by-block or frame-by-frame. In this way, m bits of compressed data are used to represent each nxc3x97n block of pixel data. Other systems utilize an adaptive compression method wherein color video data is examined block-by-block, and the type of compression to be used is then determined for each block. In one known system, two diverse colors for each block are determined by averaging the colors that are above and below the mean luminance for the block. These two computed colors may then be compared to a threshold value in order to determine the number of colors to be stored for the block.
Another method of compressing and decompressing a stream of video data is disclosed in U.S. Pat. No. 5,625,759. In this patent, each frame of video is broken up into blocks of pixels, and then the number of colors in the block is minimized by collapsing colors which are not substantially different from the colors of neighboring pixels into the color of the neighboring pixel.
While each of the methods described above usefully compress video data where the color data consists of xe2x80x9ceight-bitxe2x80x9d data, the use of such data may lead to unwanted artifacts during playback. Such artifacts can be readily observed in background scenes, such as where a plane is silhouetted against a cloudy sky. In such a visual scene, compression of the colors may cause streaking or banding of the colors in the scene.
It is well known that many of the visual artifacts observed in scenes created using compressed eight-bit color data can be suppressed using color data wherein the colors are described using twenty-bit or higher color definitions. However, until now, the use of such higher data definitions negated any advantage obtained in compressing the color data, since, for example, twenty-four bit color data requires three times as much data storage as does eight-bit color data.
What is needed in the art is a method of compressing and decompressing color video data so that the recreated video image accurately reflects the colors of the original video image while reducing the amount of data necessary so as to produce moving color images in real time from storage devices having a fixed data rate. In particular what has been needed is a method of compressing color video data consisting of higher resolution color data, such as twenty-bit (or more) color data, such that the storage space required for the resulting compressed color data is approximately the same as that required for previously available compressed eight-bit color data. Using such a method, the video stream should be capable of producing essentially artifact-free visual scenes without incurring a penalty of increased storage resources. Moreover, the increased resolution and freedom from artifacts is obtained without lagging behind the video display. The present invention meets these needs.
The present invention is directed towards a method for compressing color video data for storage using the colors of the original video image.
In an embodiment of the invention, the method of compressing color video data comprises the steps of dividing a color video frame into blocks of color video data; determining the colors present in a block; calculating a minimum number of colors necessary for the block according to a color threshold; and storing the color video data in the block in accordance with the minimum number of colors necessary for the block, wherein the minimum number of colors is less than or equal to a predetermined number.
The minimum number of colors necessary for the block can be calculated by sorting the determined colors present in the block by frequency of occurrence of each color; comparing each of the determined colors to each other determined color; ascertaining comparatively close colors from the comparison of each determined color in accordance with the color threshold; and substituting the more frequently occurring color for the less frequently occurring color of two comparatively close colors.
If the calculated minimum number of colors is greater than four, then the color threshold can be adjusted and the minimum number of colors necessary for the block can be recalculated accordingly.
The step of determining the colors present in the block may further include the step of comparing each pixel in the block to the corresponding pixel in the next previous adjacent block. Where all of the colors in the next previous adjacent block are substantially similar, within a predetermined threshold of similarity, the data stream is encoded to indicate that the same colors may be used in the current block as were used in the next previous adjacent block, thus negating the need to store color video data to describe the pixels in the current block.
The step of determining the colors present in the block can further include the step of comparing the colors present in the block with the colors in a corresponding block in a previous video frame, wherein the color is given a zero value if the difference between the colors present in the block and the colors in the corresponding block is less than a transparent threshold value.
In a further embodiment, the present invention may further optimize the compression and decompression of the video color data by determining if the color to be compressed or decompressed is a so-called xe2x80x9ccommonxe2x80x9d color that is already stored in a FIFO buffer. If the color is already stored in the buffer, then the compressor need only store an index value for that color, rather than an entire set of color bytes describing that color, thus reducing by two the number of bytes required to store each xe2x80x9ccommonxe2x80x9d color. When decompressing the video data stream, one of the bits in one of the color bytes may be used as a flag to indicate to the decompression system that the value contained in the color byte is an index value to the color stored in the FIFO buffer.
When reading data from storage devices having a fixed data rate, full motion video images can appear jerky and unnatural where the frame contains more video data than can be read at the fixed data rate given the time allotted for displaying the frame. In order to achieve smooth playback of moving video images, the amount of data being read from storage devices such as a CD-ROM should be decreased so as to allow the processor to capture a sufficient amount of the color video data to reproduce full motion video in real time.
In addition, in even high density storage devices, there is still a practical limit to the amount of data that can be stored. Compression of color video data can allow an increased number of video frames to be stored, thereby increasing the playing time of the device.
Other features and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, which illustrate, by way of example, the principles of the invention.